package algorithm_demo.demo04.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 图
 * 1. 由点的集合和边的集合构成
 * 2. 虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
 * 3. 边上可能带有权值
 *
 * 图结构的表达
 * 1. 邻接表法
 * 2. 邻接矩阵法
 * 3. 除此之外还有其他众多的方式
 *
 *
 * 图的面试题如何搞定
 * 图的算法不算难，只不过coding的代价比较高
 * 1. 先用自己最熟练的方式，实现图结构的表达
 * 2. 在自己熟悉的结构上，实现所有常用的图算法作为模板
 * 3. 把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可
 *
 *
 * @author Api
 * @date 2023/2/18 17:45
 */
public class Graph {
    HashMap<Integer,Node> nodes; // key:节点编号  value：节点
    Set<Edge> edges;
    public Graph(){
        this.nodes=new HashMap<Integer, Node>();
        this.edges=new HashSet<Edge>();
    }

    /** 根据数据 生成一张图. matrix的列值对应  [weight，from，to]  */
    //matrix所有的边
    //N*3的矩阵
    //[weight, from节点上面的值，to节点上面的值]
    public static Graph createGraph(Integer[][] matrix){
        Graph graph=new Graph();
        for (Integer[] integers : matrix) {
            Integer weight = integers[0];
            Integer from = integers[1];
            Integer to = integers[2];
            //判断是图中是否存在该节点
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode);

            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}
